\chapter{Вопрос №13}

Комбинаторный смысл произведения обыкновенных и экспоненциальных производящих функций. Примеры.

\section{Произведение опф}

Пусть имеются две опф:
\[
	\begin{split}
		&f\left(x\right) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... \\
		&g\left(x\right) = b_0 + b_1 x + b_2 x^2 + b_3 x^3 + ...
	\end{split}
\]
Произведением этих опф будет опф:
\[
	\begin{split}
		&h\left(x\right) = c_0 + c_1 x + c_2 x^3 + c_3 x^3 + ... \\
		& c_n = \sum_{i=0}^{n}a_ib_{n-i}
	\end{split}
\]
Комбинаторный смысл такого произведения в следующем, мы берем линейно-упорядоченное множество, и делим его на две чати относительно некоторой границы, т. е. все элементы которые меньше границы отходят в первую часть, а все элементы, которые больше отходят во вторую часть. После этого над первой частю совершаем некоторое действие $a_n$ способами (где $n$ - количество элементов в первой части), а во второй части $b_k$ способами (где $k$ - количество элементов во второй части), а все произведение описывает нам количество способов совершить такое действие над множеством из $n+k$ элементов, для всех значений $n+k$.

Пример: семестр преподавателя поделен на две опследовательные части - теория и практика (первая часть семестра посвящена теории, а вторая практике). Во время теоретической части преподаватель может выделить 2 дня на командировку, а во время практической части 3 дня, сколькими способами можно разбить семестр на 3 части и выбрать дни на командировку, если всего в семетре $n$ дней.

Производящая функция для количества способов выбрать 2 дня на командировки выглядит следующим образом:
\[
	f\left(x\right) = \sum_{k=0}^\infty \binom{k}{2} x^k
\]
для количества способов выбрать 3 дня на командировки очевидно получаем:
\[
	f\left(x\right) = \sum_{k=0}^\infty \binom{k}{3} x^k
\]
Произведение $h\left(x\right)$ - опф функция описывающая требуемое решение:
\[
	h\left(x\right) = \sum_{k=0}^\infty \sum_{i=0}^k \binom{i}{2}\binom{k-i}{3}
\]
теперь найдем более компактную запись, для этого распишем:
\[
	\begin{split}
		&\binom{k}{2} = \frac{k\cdot\left(k-1\right)}{2} \\
		&\binom{k}{3} = \frac{k\cdot\left(k-1\right)\cdot\left(k-2\right)}{6}
	\end{split}
\]
рассмотрим теперь 2 и 3 производные функции $\frac{1}{1-x}$:
\[
	\begin{split}
		&\left(\frac{1}{1-x}\right)'' = \frac{2}{\left(1-x\right)^3} = \sum_{n=0}^\infty n\left(n-1\right) x^{n-2} \Leftrightarrow \\
		& f\left(x\right) = \frac{x^2}{\left(1-x\right)^3}
	\end{split}
\]
далее
\[
	\begin{split}
		&\left(\frac{1}{1-x}\right)''' = \frac{6}{\left(1-x\right)^4} = \sum_{n=0}^\infty n\left(n-1\right)\left(n-2\right)x^{n-3} \Leftrightarrow \\
		& g\left(x\right) = \frac{x^3}{\left(1-x\right)^4}
	\end{split}
\]
а тогда имеем:
\[
	\begin{split}
		h\left(x\right) = \frac{x^5}{\left(1-x\right)^7} = x^5 \sum_{n=0}^\infty \Binomrep{7}{n} x^n = x^5\sum_{n=0}^\infty \binom{n+6}{6} x^n
	\end{split}
\]
\section{Произведение эпф}

Пусть имеется 2 эпф:
\[
	\begin{split}
		& F\left(x\right) = a_0 + a_1 x + a_2 \frac{x^2}{2} + a_3 \frac{x^3}{3!} + ...\\
		& G\left(x\right) = b_0 + b_1 x + b_2 \frac{x^2}{2} + b_3 \frac{x^3}{3!} + ...
	\end{split}
\]
произведение этих эпф будет эпф:
\[
	\begin{split}
		& H\left(x\right) = c_0 + c_1 x + c_2 \frac{x^2}{x} + c_3 \frac{x^3}{3!} + ...\\
		& c_n = \sum_{i=0}^n \binom{n}{i}a_ib_{n-i}
	\end{split}
\]
как видно, от произведение опф произведение эпф отличается наличием биномиального множителя, который позволяет снять ограничение лиейной упорядоченности множества и работать с произвольными разбиениями множеств, в остальном смысл произведения эпф совпадает со смыслом произведения опф.

В качестве примера рассмотрим предыдующую задачу, но теперь дни практики и дни теории могут идти в перемешку.

Рассмотрим эпф для выбора 2 командировачных дня:
\[
	\begin{split}
		& F\left(x\right) = \sum_{n=0}^\infty \frac{n\left(n-1\right)}{2} \frac{x^n}{n!} = \sum_{n=0}^\infty \frac{1}{2} \frac{x^n}{\left(n-2\right)!} = \\
		& = \frac{x^2}{2} exp\left(x\right)
	\end{split}
\]
и для выбора 3 командировачных дня:
\[
	\begin{split}
		& G\left(x\right) = \sum_{n=0}^\infty \frac{n\left(n-1\right)\left(n-2\right)}{6} \frac{x^n}{n!} = \sum_{n=0}^\infty \frac{1}{6} \frac{x^n}{\left(n-3\right)!} = \\
		& = \frac{x^3}{6} exp\left(x\right)
	\end{split}
\]
в произведении имеем:
\[
	H\left(x\right) = \frac{x^5}{12} exp\left(2x\right) = \frac{x^5}{12} \sum_{k=0}^\infty 2^k \frac{x^k}{k!}
\]
